package 数组;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/3sum/
 */
public class _15_三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums); //先排序
        return nSumTarget(nums,3,0,0); //相加和等0
    }


    /**
     * n数之和万能模板
     * @param nums 传入的数组
     * @param n 几数之和
     * @param start 起始
     * @param target 目标和
     * @return
     */
    private List<List<Integer>> nSumTarget(int[] nums,int n,int start,int target){
        int size = nums.length; //数组元素个数
        List<List<Integer>> res = new ArrayList<>();
        if(n<2 || size<n) return null; //特殊情况
        if(n == 2){ //base Case
            int lo = start,hi = size - 1;
            List<Integer> tmp = new ArrayList<>();
            while(lo<hi){
                int sum = nums[lo] + nums[hi];
                int left = nums[lo],right = nums[hi]; //记录当前值
                if(sum<target){
                    while(lo<hi && nums[lo] == left) lo++; //跳过相同的元素
                }else if(sum>target){
                    while(lo<hi && nums[hi] == right) hi--;
                }else{ //找到的情况
                    tmp.add(left);
                    tmp.add(right);
                    while(lo<hi && nums[lo] == left) lo++;
                    while(lo<hi && nums[hi] == right) hi--;
                }
            }
        }else{ //n>2,递归计数(n-1)Sum
            for(int i=start;i<size;++i){
                //穷举任意一个数，然后变成找两数之和的问题
                List<List<Integer>> sub = nSumTarget(nums,n-1,i+1,target-nums[i]);
                for (List<Integer> integers : sub) {
                    //(n-1)Sum 加上 nums[i] 就是 nSum
                    integers.add(nums[i]);
                    res.add(integers);
                }
                //跳过第一个数字重复的情况
                while(i<size-1 && nums[i] == nums[i+1]) i++;
            }
        }
        return res;
    }
}
